This invention relates to run length encoding and decoding for raster scanned imaging systems and, more particularly, to methods and means for highlighting the boundaries between serial run length message codes of variable length.
Raster scanned imaging systems often are data rate limited. For example, conventional facsimile systems typically depend on limited bandwith communications channels, such as are provided by the public switched telephone network. Accordingly, to increase the throughput of those systems, substantial effort and expense have been devoted to the development of data compression and decompression techniques for eliminating and then restoring the redundant information that is commonly found in video signals having a raster scan format -- viz., signals comprising a predetermined number of serial picture elements for each of a plurality of successive, substantially equidistantly spaced scan lines. Of course, in facsimile systems, throughput is customarily expressed in terms of a document transmission time.
Others have recognized that run length encoding and decoding may be employed in digital raster scanned imaging systems for compressing and decompressing, respectively, binary video signals. In that context, a "run" is classically defined as being an uninterrupted series of picture elements of the same logic level. Thus, run length encoding is utilized to convert the white and/or black runs of a binary video signal having a raster scan format into corresponding run length message codes. Conversely, run length decoding is a complementary process for reconverting those message codes into white and/or black runs of the appropriate length to reconstruct the video signal.
As a general rule, the run length message codes are of variable length (i.e., bit count) to optimize, or at least increase, the data compression. Moreover, the run length message codes are usually serially fed from the encoder to the decoder. Consequently, others have addressed the problem of discriminating between run length message codes of variable length in a serial data stream.
More particularly, it has been suggested that flag codes be inserted into the data stream to separate the run length message codes. That is, however, counterproductive because the additional bits comprised by the flag codes detract from the increased throughput capability offered by the data compression. Another, more sophisticated proposal is to employ mutually exclusive run length message codes so that each code is distinguishable from the prefixes of all other codes. That approach is taken in constructing what are commonly referred to as "Huffman codes", thereby acknowledging D. A. Huffman, "A Method for the Construction of Minimum -- Redundance Codes", Proceedings of the I.R.E., September 1952, pp. 1098-1101. A mutually exclusive or Huffman-type code set has substantial merit, but the complexity of the code set rapidly increases as additional codes are added.